package main

import (
	"fmt"
	"strings"
)

//@url: https://leetcode-cn.com/problems/largest-1-bordered-square/

func largest1BorderedSquare(grid [][]int) int {
	maxLen := grid[0][0]
	for i := 0; i < len(grid); i++ {
		for j := 1; j < len(grid[i]); j++ {
			if maxLen == 0 && grid[i][j-1] == 1 {
				maxLen = 1
			}
			if grid[i][j] == 0 {
				continue
			}
			grid[i][j] += grid[i][j-1]
			//校验最大边长是否成立
			value := grid[i][j]
			if value < maxLen {
				continue
			}
			value = min(value, upValueOneCount(grid, i, j, value))
			//println(i, j, value, num, upValueOneCount(grid, i, j-value+1, value))
			for maxLen < value {
				if checkSquare(grid, i, j, value) {
					maxLen = max(value, maxLen)
					break
				}
				value--
			}

		}
	}
	//fmt.Println("---- this is fuck cut ----")
	//printTwoArr(grid)
	return maxLen * maxLen
}

func checkSquare(grid [][]int, i int, j int, value int) bool {
	if upValueOneCount(grid, i, j-value+1, value) >= value {
		if grid[i-value+1][j] >= value {
			return true
		}
	}
	return false
}

//向上遍历 判断连续1的个数
//该方法可做cache优化
func upValueOneCount(grid [][]int, i int, j int, count int) int {
	sub := i - count + 1
	if sub < 0 {
		sub = 0
	}
	num := 0
	for x := i; x >= sub; x-- {
		if grid[x][j] == 0 {
			break
		}
		num++
	}
	return num
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func printTwoArr(arr [][]int) {
	for i := range arr {
		fmt.Printf("%v \n", arr[i])
	}
}

func main() {
	println(largest1BorderedSquare([][]int{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}) == 9)
	println(largest1BorderedSquare([][]int{{1, 1, 0, 0}}) == 1)
	println(largest1BorderedSquare([][]int{{0, 0}, {1, 0}}) == 1)
	println(largest1BorderedSquare([][]int{{0, 0}, {1, 1}}) == 1)
	println(largest1BorderedSquare([][]int{{0, 1}, {1, 1}}) == 1)
	println(largest1BorderedSquare([][]int{{1, 0, 1, 0, 1}, {1, 1, 1, 0, 1}, {1, 0, 1, 1, 0}, {1, 1, 1, 1, 1}, {1, 1, 1, 1, 1}}) == 9)
	println(largest1BorderedSquare([][]int{{1, 1, 1}, {1, 1, 0}, {1, 1, 1}, {0, 1, 1}, {1, 1, 1}}) == 4)
	println(largest1BorderedSquare([][]int{{0, 1, 1, 1}, {1, 1, 1, 1}, {1, 0, 0, 1}, {1, 1, 1, 1}, {1, 0, 1, 1}, {1, 1, 0, 1}}) == 4)
	println(largest1BorderedSquare([][]int{{0, 1, 1, 0, 1}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 0}, {0, 0, 1, 1, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 1}, {0, 1, 1, 1, 1}}) == 9)
	println(largest1BorderedSquare([][]int{{0, 1, 1, 1, 1, 0}, {1, 1, 0, 1, 1, 0}, {1, 1, 0, 1, 0, 1}, {1, 1, 0, 1, 1, 1}, {1, 1, 0, 1, 1, 1}, {1, 1, 1, 1, 1, 1}, {1, 0, 1, 1, 1, 1}, {0, 0, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1}}) == 16)

	//println(util("[[0,1,1,1,1,0],[1,1,0,1,1,0],[1,1,0,1,0,1],[1,1,0,1,1,1],[1,1,0,1,1,1],[1,1,1,1,1,1],[1,0,1,1,1,1],[0,0,1,1,1,1],[1,1,1,1,1,1]]"))
}

func util(str string) string {
	return strings.Replace(strings.Replace(str, "[", "{", -1), "]", "}", -1)
}
